/**
 * QuickSort.java created by zhangzhidong 
 * at 下午8:07:23 2016年7月6日
 */
package algorithm;

import java.util.Arrays;

/**
 * @author zhangzhidong<br>
 * comment generated at 2016年7月6日下午8:07:23<br>
 * 
 */
public class QuickSort {

	/**
	 * 下午8:07:23 2016年7月6日
	 * @param args
	 */
	public static void main(String[] args) {
		int arr [] = new int []{5,2,7,8,1,6,3,9,0,-1,10,66,88,4,-2,99,-11,45,33};
//		int arr [] = new int[]{1,5,5,5,5,5,5};
		quickSort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	static int partition(int arr[],int left , int right){
		int pivot = arr[left];
		while(left<right){
			while(left<right && arr[left]>pivot) left++;
			while(right>left && arr[right]<pivot) right--;
			if(left < right){
				if(arr[left]==arr[right]){
					left ++;
				}else{
					swap(arr,left,right);	
				}
				
			}
		}
		arr[left] = pivot;
		return left;
	}
	static void swap(int arr[],int left,int right){
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;
	}
	static void quickSort(int arr[],int left,int right){
		if(left>=right){
			return;
		}
		int low = partition(arr, left, right);
		quickSort(arr,left,low-1);
		quickSort(arr,low+1,right);
	}
	

}
